#include "heap4.h"
#include <string.h>


/*
内存策略 4 申请,释放，还合并空闲内存

xBlockSize = 请求大小 + 结构体大小
HEAP中，结构体在前，数据区紧挨着结构体
 */

#define configADJUSTED_HEAP_SIZE  ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )


#if   portBYTE_ALIGNMENT == 32
	#define portBYTE_ALIGNMENT_MASK ( 0x001f )
#elif portBYTE_ALIGNMENT == 16
	#define portBYTE_ALIGNMENT_MASK ( 0x000f )
#elif portBYTE_ALIGNMENT == 8
	#define portBYTE_ALIGNMENT_MASK ( 0x0007 )
#elif portBYTE_ALIGNMENT == 4
	#define portBYTE_ALIGNMENT_MASK	( 0x0003 )
#elif portBYTE_ALIGNMENT == 2
	#define portBYTE_ALIGNMENT_MASK	( 0x0001 )
#elif portBYTE_ALIGNMENT == 1
	#define portBYTE_ALIGNMENT_MASK	( 0x0000 )
#endif

/* Block sizes must not get too small. */
#define heapMINIMUM_BLOCK_SIZE	( ( size_t ) ( xHeapStructSize << 1 ) )
#define heapBITS_PER_BYTE		(8u)

typedef struct A_BLOCK_LINK
{
	struct A_BLOCK_LINK *pxNextFreeBlock;	/*<< The next free block in the list. */
	size_t xBlockSize;						        /*<< The size of the free block. */
} BlockLink_t;

//!< 表示当前系统中未分配的内存堆大小
static size_t xFreeBytesRemaining = 0U;
//!< 表示未分配内存堆空间历史最小的内存值
static size_t xMinimumEverFreeBytesRemaining = 0U;
/*   The size of the structure placed at the beginning of each allocated memory
     block must by correctly byte aligned. */
static const size_t xHeapStructSize	= ( sizeof( BlockLink_t ) + ( ( size_t ) ( portBYTE_ALIGNMENT - 1 ) ) ) & ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
//<! xStart始终指向HEAP的第一个块，xEnd指向HEAP的最后一个块
static BlockLink_t xStart, *pxEnd = NULL;
/* Gets set to the top bit of an size_t type.  When this bit in the xBlockSize
member of an BlockLink_t structure is set then the block belongs to the
application.  When the bit is free the block is still part of the free heap
space. */
static size_t xBlockAllocatedBit = 0;


uint8_t ucHeap[ configTOTAL_HEAP_SIZE ] = { 0 };


static void prvHeapInit( void )
{
  BlockLink_t *pxFirstFreeBlock;
  uint8_t *pucAlignedHeap;
  size_t uxAddress;
  size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;

	/* Ensure the heap starts on a correctly aligned boundary. */
	uxAddress = ( size_t ) ucHeap;

	if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
	{
		uxAddress += ( portBYTE_ALIGNMENT - 1 );
		uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
		xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
	}

	pucAlignedHeap = ( uint8_t * ) uxAddress;

	/* xStart is used to hold a pointer to the first item in the list of free
	blocks.  The void cast is used to prevent compiler warnings. */
	xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
	xStart.xBlockSize = ( size_t ) 0;

	/* pxEnd is used to mark the end of the list of free blocks and is inserted
	at the end of the heap space. */
	uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
	uxAddress -= xHeapStructSize;
	uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
	pxEnd = ( void * ) uxAddress;
	pxEnd->xBlockSize = 0;
	pxEnd->pxNextFreeBlock = NULL;

	/* To start with there is a single free block that is sized to take up the
	entire heap space, minus the space taken by pxEnd. */
	pxFirstFreeBlock = ( void * ) pucAlignedHeap;
	pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
	pxFirstFreeBlock->pxNextFreeBlock = pxEnd;

	/* Only one block exists - and it covers the entire usable heap space. */
	xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
	xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;

	/* Work out the position of the top bit in a size_t variable. */
	xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}

static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
	/*
	 * pxIterator	   指向首块可用的内存空间
	 * pxBlockToInsert MALLOC申请内存后的一块空间
	 * */
	 BlockLink_t *pxIterator;
	 uint8_t *puc;



	/*
	 * 重要前提， xStar 链表中的都是空闲内存
	 * 先遍历空闲内存表，找到满足这种顺序的pxIterator
	 * pxIterator <= pxBlockToInsert <= pxIterator->pxNextFreeBlock
	 * 此时，pxIterator为插入内存之前的空闲内存，pxNextFreeBlock为插入内存之后的空闲内存
	 * */
	for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
	{
	}


// pxBlockToInsert 开始融合前后的内存
	/*
	 * 如果插入内存之前有相邻空闲线内存，那么两块内存合并，要插入内存会指向合并后的首地址
	 */
	puc = ( uint8_t * ) pxIterator;
	if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
	{
		pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
		pxBlockToInsert = pxIterator;
	}


	/*
	 * 如果插入内存之后有相邻空闲空内存，那么也会两块合并
	 * 如果不相邻，那就直接往里插了
	 * 插完后，除非前面有内存融合，否则遵循 pxIterator -> pxBlockToInsert -> pxNextFreeBlock
	 */
	puc = ( uint8_t * ) pxBlockToInsert;
	if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
	{
		if( pxIterator->pxNextFreeBlock != pxEnd )
		{
			//!< 没有连到尾节点上
			pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
			pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
		}
		else
		{
			//!< 连到尾节点上了
			pxBlockToInsert->pxNextFreeBlock = pxEnd;
		}
	}
	else
	{
    //!< 后面不响相邻，直接往里插
		pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
	}

	if( pxIterator != pxBlockToInsert )
	{
		pxIterator->pxNextFreeBlock = pxBlockToInsert;
	}
// pxBlockToInsert 结束融合后的内存

}

void *pvPortMalloc( size_t xWantedSize )
{

	BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
	void *pvReturn = NULL;

	//!< 第一次调用需要初始化HEAP
	if( pxEnd == NULL )
	{
		prvHeapInit();
	}

	//!< xWantedSize 的最高位不为1
	if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
	{
		//!< 管理堆的结构体也存在堆里，所以要额外加上它
		if( xWantedSize > 0 )
		{
			xWantedSize += xHeapStructSize;

			// 保证请求数据的大小对齐
			if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
			{
				xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
			}
		}
    else
    {
    	//!< size_t为无符号类型，理论上说永远到不了这里
        return NULL;
    }


			if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
			{
				//!< 遍历空闲链表，寻找一个可以用的块
				pxPreviousBlock = &xStart;
				pxBlock = xStart.pxNextFreeBlock;
				while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
				{
					pxPreviousBlock = pxBlock;
					pxBlock = pxBlock->pxNextFreeBlock;
				}

				/* If the end marker was reached then a block of adequate size
				was	not found. */
				if( pxBlock != pxEnd )
				{
					/*
          	  	  	  记住, HEAP中的内存先放链表头，再接指向的内存
          	  	  	  pvReturn指向返回的内存地址。
					*/
				  pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );

					//!< 这个内存块被使用到了,先从空闲链表中移除.等内存切割完后再追加回来
					pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

					//!< 开始内存切割，如果申请完后的内存足够大(2表头)，则将多余内存返回链表
					if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
					{
							//!< 去除分配出去的内存(这里包括了表头大小), pxBlock指向将被分配的内存
						pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
						pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
						pxBlock->xBlockSize = xWantedSize;

						//!< 将 切割完成后的剩余内存重新追加回来
						prvInsertBlockIntoFreeList( pxNewBlockLink );
					}
					else
					{
						//!< 没有可以继续分割的内存了
					}

					xFreeBytesRemaining -= pxBlock->xBlockSize;
					if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
					{
						xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
					}

					// xBlockSize最高位设置为1，表明此内存已经被占用
					pxBlock->xBlockSize |= xBlockAllocatedBit;
					pxBlock->pxNextFreeBlock = NULL;		// here
				}
				else
				{
					//<! 理论上这里无法到达
					return NULL;
				}
			}
			else
			{
				//<! 没有空闲的内存了
				return NULL;
			}
		}

	   return pvReturn;
}

void vPortFree( void *pv )
{
  uint8_t *puc = ( uint8_t * ) pv;
  BlockLink_t *pxLink;

	if( pv != NULL )
	{
		/* The memory being freed will have an BlockLink_t structure immediately
		before it. */
		puc -= xHeapStructSize;

		/* This casting is to keep the compiler from issuing warnings. */
		pxLink = ( void * ) puc;


		if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
		{
			if( pxLink->pxNextFreeBlock == NULL )
			{
				/* The block is being returned to the heap - it is no longer
				allocated. */
				pxLink->xBlockSize &= ~xBlockAllocatedBit;

        /* Add this block to the list of free blocks. */
				xFreeBytesRemaining += pxLink->xBlockSize;
				prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
			}
			else
			{
				//!< 正常被分配后的内存都不属于链表中
			}
		}
		else
		{
			//!< 没有应用占有它
		}
	}
}



void *pvCalloc(size_t nitems, size_t size)
{
	size_t length;
	uint8_t *p;

	length = nitems *  size;
	p = pvPortMalloc( length );
	memset( p , 0, length );

	return p;
}


void *pvRealloc(void *ptr, size_t size)
{
	uint8_t *p;
	uint32_t length;
	p = pvPortMalloc( size );
	length = *((uint32_t *)ptr - 1) & (0x7fffffff);
	if( size < length )
		length = size;
	memcpy( p, ptr, length );
	vPortFree( ptr );

	return p;
}
